﻿// 象 BISHOPS.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
/*
https://algospot.com/judge/problem/read/BISHOPS

问题
"找到一种在N*N的棋盘上放置皇后，使它们彼此不受攻击的方法。"

以上问题是著名的N皇后问题。LIBe在数据结构课上解决N皇后问题并掌握了回溯法，为了寻找更困难的问题来挑战自己，他将问题修改为以下形式:

"在有障碍物的棋盘上，皇后不能越过障碍物时，能够放置的最多皇后数量是多少？"

然而，事情并不总是按计划进行。由于编码技能不足，LIBe放弃了解决这个问题，并最终将问题改为以下形式:

"在有障碍物的棋盘上，象棋主教不能越过障碍物时，能够放置的最多的主教数量是多少？"

LIBe能够解决这个问题吗？

输入
输入包含多个测试用例。输入的第一行是测试用例的数量T。
每个测试用例的第一行包含棋盘的大小N (1 <= N <= 8)。
之后的N行表示棋盘的状态。'.'表示可以放置主教的有效位置，'*'表示障碍物。

输出
对于每个测试用例，输出可放置的最大主教数量。

示例输入
3
5
.....
.....
.....
.....
.....
8
....
..*
*....*
.*..*
.**..*
..**..
.....*
*...
8
....
....
....
....
....
....
....
....

示例输出
8
18
7
*/
int main()
{
    std::cout << "Hello World!\n";
}

 
